package com.aqie.easy.hash;

/**
 * 204 计算质数  小于非负整数 n 的质数
 */
public class CountPrimes {
    /**
     * 1，厄拉多塞筛法 34ms
     * @param n
     * @return
     */
    public int countPrimes2(int n) {
        int[] nums = new int[n];
        for (int i = 2; i < nums.length; i++) {
            nums[i] = 1;
        }
        for (int i = 2; i * i < nums.length; i++) {
            if (nums[i] == 1) {
                for (int j = i * i; j < nums.length; j += i) {
                    nums[j] = 0;
                }
            }
        }
        int sum = 0;
        for (int i = 2; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }

    /**
     * 3,欧拉算法 44ms
     * @param n
     * @return
     */
    public int countPrimes3(int n) {
        byte[] check = new byte[n];//用来标记是否已经访问过了，如果访问过了就打1，没访问过打0
        int[] primeList = new int[n]; //用来记素数


        int count = 0;//用来记录素数个数
        for(int i = 2;i< n;i++) {
            if(check[i]==0) {    //打了1的就不会再看了，重复赋值浪费时间
                primeList[count++] = i; //count变量记录素数个数，数组记录已知的素数的值
            }

            for(int j=0;j<count&&i*primeList[j]<n;j++) {
                if(i*primeList[j]>n) {
                    break;
                }

                check[i*primeList[j]] = 1; //标记 x=i*primeList[j],x位置是我访问过的位置，打1
                if(i%primeList[j]==0) {   //这一部分不好理解，比方说6，之前访问过（2,3），那么6%2==0,不用再检查6%3了，真正负责记录数据的是count变量
                    break;
                }
            }
        }
        return count;
    }





    /**
     * 2, 超时
     * @param n
     * @return
     */
    public int countPrimes(int n) {
        int count = 0;
        for (int i = 1; i < n; i++) {
            if (isPrime(i)) count++;
        }
        return count;
    }

    private boolean isPrime(int num) {
        if (num <= 1) return false;
        // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}
